Deriving the Fibonacci doubling formulas combinatorially

This post provides a quick derivation of the fast Fibonacci doubling formulas, using the correspondence between Fibonacci numbers and the number of ways to climb $n$ steps taking 1 or 2 steps at a time.

The Fibonacci numbers are a sequence $\mathrm{Fib}(i)$ defined by $\mathrm{Fib}(1)=\mathrm{Fib}(2)=1$ and $\mathrm{Fib}(n+2)=\mathrm{Fib}(n+1)+\mathrm{Fib}(n)$.

The Fibonacci doubling formulas are:

$$\begin{array}{rcl}\mathrm{Fib}(2n)& =& 2\mathrm{Fib}(n)\mathrm{Fib}(n+1)-\mathrm{Fib}(n{)}^2\\ \mathrm{Fib}(2n+1)& =& \mathrm{Fib}(n+1{)}^2+\mathrm{Fib}(n{)}^2\end{array}$$

These formulas can be used to efficiently compute Fibonacci numbers (see the the end of the post for how). They are usually derived from a matrix power representation of Fibonacci numbers (or see one of my earlier posts for an alternative). This blog post gives a direct combinatorial derivation.

There’s a well-known algorithmic problem of counting the number of ways, $S(n)$, to climb $n$ steps, starting at the first step, ending exactly on the $n$th step, and taking 1 or 2 steps at a time. We see that $S(1)=S(2)=1$, and $S(n+2)=S(n+1)+S(n)$. Since this problem has the exact same recurrence relation as the Fibonacci numbers, $S(n)=\mathrm{Fib}(n)$.

We can count solutions to the steps problem in a different way, by dividing the problem in two (treating even and odd separately).

First the even case. Suppose we have $2n$ steps. The number of ways of taking these steps landing on the $n$th step is $S(n)S(n+1)$ (the number of ways of reaching step $n$, times the number ways of climbing $n+1$ steps). If a path doesn’t land on step $n$, then it must land on step $n-1$ and jump over step $n$ to land on step $n+1$. The number of such paths is $S(n-1)S(n)$. Thus $S(2n)=S(n)S(n+1)+S(n-1)S(n)$. Since $S(n-1)+S(n)=S(n+1)$, we have $S(2n)=S(n)S(n+1)+(S(n+1)-S(n))S(n)=2S(n)S(n+1)-S(n{)}^2$.

The odd case is similar. Suppose we have $2n+1$ steps. By similar arguments to above, there are $S(n+1)S(n+1)$ paths that land on step $n+1$, and $S(n)S(n)$ paths that don’t. Thus $S(2n+1)=S(n+1{)}^2+S(n{)}^2$.

Since $S=\mathrm{Fib}$, we’ve already derived the doubling formulas:

$$\begin{array}{rcl}\mathrm{Fib}(2n)& =& 2\mathrm{Fib}(n)\mathrm{Fib}(n+1)-\mathrm{Fib}(n{)}^2\\ \mathrm{Fib}(2n+1)& =& \mathrm{Fib}(n+1{)}^2+\mathrm{Fib}(n{)}^2\end{array}$$

For completeness, here’s how to use these formulae to quickly compute Fibonacci numbers with $O({\log }_2(n))$ arithmetic operations.

def fib2(n):
	"""fib2(n) returns fib(n), fib(n+1)"""
	if n == 0:
        return 0, 1
	f0, f1 = fib2(n//2)
	if n % 2 == 0:
        # Even case.
        return 2*f0*f1 - f0*f0, f0*f0 + f1*f1
	else: 
        # Odd case.
        # We need to return fib(2k+1), fib(2k+2) 
        # and we have f0=fib(k), f1=fib(k+1).
        # The doubling formulas give:
        # fib(2k) = 2*f0*f1 - f0*f0, fib(2k+1)=f0*f0 + f1*f1
        # Then fib(2k+2) = fib(2k) + fib(2k+1) = 2*f0*f1 + f1*f1.
        return f0*f0 + f1*f1, 2*f0*f1 + f1*f1

for i in range(20):
	print(i, fib2(i)[0])